/*
============================================================================
 Name        : dd_rbtree.c
 Author      : Jian (raphyer@hotmail.com)
 Version     :
 Copyright   : GPL
 Description : dd_rbtree.c - source file
============================================================================
*/

/* INCLUDE FILES */
#include "dd_rbtree.h"
#include "dd_stack.h"

/* MACROS */

#define _path_clear(p)      dd_stack_reset(p)
#define _path_count(p)      dd_stack_count(p)
#define _path_add(p,n)      dd_stack_push(p, n)
#define _path_remove(p)     ((dd_rbtree_node*)(dd_stack_pop(p)))
#define _path_removen(p,n)  dd_stack_popn(p,n)
#define _path_top(p)        ((dd_rbtree_node*)(dd_stack_top(p)))
#define _path_datan(p,n)    ((dd_rbtree_node*)(dd_stack_datan(p,n)))


typedef enum __dd_rbtree_color {
    EColorRed = 0,
    EColorBlack
}dd_rbtree_color;


static dd_rbtree_node* _init_node(dd_rbtree_key* key, dd_rbtree_value* value)
{
    dd_rbtree_node* node = (dd_rbtree_node*)DD_MALLOC(sizeof(dd_rbtree_node)) ;
    node->key            = key ;
    node->value          = value ;
    node->left_child     = DD_NULL ;
    node->right_child    = DD_NULL ;
    node->color          = EColorRed ;
    return node ;
}

static void _deinit_node(dd_rbtree_node* node)
{
    if (node) {
        _deinit_node(node->left_child) ;
        _deinit_node(node->right_child) ;
        __do_destroy(node) ;
    }
}

static void _deinit_empty_node(dd_rbtree_node* node)
{
    if (node) {
        __do_destroy(node) ;
    }
}

static __dd_inline__ void _change_color(dd_rbtree_node* node, dd_rbtree_color color) 
{
    __DD_ASSERT_DEFENSE(node, return) ;
    node->color = color ;
}

static __dd_inline__ DD_BOOL _is_left_child(const dd_rbtree_node* node, const dd_rbtree_node* parent)
{
    DD_BOOL ret = (parent->left_child == node) ; 
    
    __DD_ASSERT(ret || parent->right_child == node) ;

    if (!(ret || parent->right_child == node))
    {
        int zzz = 1; 
    }

    return ret;
}


static __dd_inline__ DD_BOOL _is_leaf(const dd_rbtree_node* node)
{
    return (!node->left_child) && (!node->right_child) ; 
}


static void _change_child_in_path(dd_rbtree_tree* rbtree, dd_rbtree_node* new_child, dd_rbtree_node* old_child)
{
    if (_path_count(rbtree->path) == 0) {
        __DD_ASSERT(old_child == rbtree->root) ;
        rbtree->root = new_child ;
    }
    else {
        dd_rbtree_node* parent = _path_remove(rbtree->path) ;
        if (_is_left_child(old_child, parent)) 
            parent->left_child  = new_child ;
        else 
            parent->right_child = new_child ;
    }
}


static void _left_left(dd_rbtree_tree* rbtree)
{
    dd_rbtree_node* cur     = _path_remove(rbtree->path) ;
    dd_rbtree_node* parent  = _path_remove(rbtree->path) ;
    dd_rbtree_node* grandpa = _path_remove(rbtree->path) ;
    
    grandpa->left_child     = parent->right_child ;
    parent->right_child     = grandpa ;

    _change_color(parent, EColorBlack) ;
    _change_color(grandpa, EColorRed) ;

    _change_child_in_path(rbtree, parent, grandpa) ;
}


static void _right_right(dd_rbtree_tree* rbtree)
{
    dd_rbtree_node* cur     = _path_remove(rbtree->path) ;
    dd_rbtree_node* parent  = _path_remove(rbtree->path) ;
    dd_rbtree_node* grandpa = _path_remove(rbtree->path) ;
    
    grandpa->right_child    = parent->left_child ;
    parent->left_child      = grandpa ;

    _change_color(parent, EColorBlack) ;
    _change_color(grandpa, EColorRed) ;

    _change_child_in_path(rbtree, parent, grandpa) ;
}


static void _left_right(dd_rbtree_tree* rbtree)
{
    dd_rbtree_node* cur     = _path_remove(rbtree->path) ;
    dd_rbtree_node* parent  = _path_remove(rbtree->path) ;
    dd_rbtree_node* grandpa = _path_remove(rbtree->path) ;

    parent->right_child     = cur->left_child ;
    grandpa->left_child     = cur->right_child ;
    cur->left_child         = parent ;
    cur->right_child        = grandpa ;
    
    _change_color(cur, EColorBlack) ;
    _change_color(grandpa, EColorRed) ;

    _change_child_in_path(rbtree, cur, grandpa) ;
}


static void _right_left(dd_rbtree_tree* rbtree)
{
    dd_rbtree_node* cur     = _path_remove(rbtree->path) ;
    dd_rbtree_node* parent  = _path_remove(rbtree->path) ;
    dd_rbtree_node* grandpa = _path_remove(rbtree->path) ;

    parent->left_child      = cur->right_child ;
    grandpa->right_child    = cur->left_child ;
    cur->left_child         = grandpa ;
    cur->right_child        = parent ;

    _change_color(cur, EColorBlack) ;
    _change_color(grandpa, EColorRed) ;
    
    _change_child_in_path(rbtree, cur, grandpa) ;
}



static void _insert_check_balance(dd_rbtree_tree* rbtree)
{
    DD_INT count = _path_count(rbtree->path) ;

    if (count > 2){
        
        dd_rbtree_node* cur     = _path_datan(rbtree->path, 0) ;
        dd_rbtree_node* parent  = _path_datan(rbtree->path, 1) ;
        dd_rbtree_node* grandpa = _path_datan(rbtree->path, 2) ;
        dd_rbtree_node* uncle   = _is_left_child(parent, grandpa) ? grandpa->right_child : grandpa->left_child ;

        if (parent->color == EColorBlack) {
            /* It is the best case, the rbtree still keep balance */
            return ;
        }
       
        /* parent's color is RED */

        __DD_ASSERT_DEFENSE(grandpa->color == EColorBlack, return) ;

        if (uncle && uncle->color == EColorRed)  {
            
            _change_color(parent, EColorBlack) ;
            _change_color(uncle, EColorBlack) ;
            _change_color(grandpa, EColorRed) ;
            
            _path_removen(rbtree->path, 2) ;  /* Remove the cur and parent, now the grandpa is the top data in the stack */

            _insert_check_balance(rbtree) ;

            return ;
        }
        
        /* uncle's color is BLACK */

        if (_is_left_child(parent, grandpa)) {
           if (_is_left_child(cur, parent))
                _left_left(rbtree) ;
            else 
                _left_right(rbtree) ;
        }
        else {
            if (_is_left_child(cur, parent))
                _right_left(rbtree) ;
            else 
                _right_right(rbtree) ;
        }
    }
    else if (count == 1) {
        dd_rbtree_node* cur    = _path_remove(rbtree->path) ;
        __DD_ASSERT(cur == rbtree->root) ;
        _change_color(cur, EColorBlack) ;   /* The root must color with BLACK */ 
    }
    else if (count == 2) {
        dd_rbtree_node* cur    = _path_remove(rbtree->path) ;
        dd_rbtree_node* parent = _path_remove(rbtree->path) ;
        
        __DD_ASSERT(cur->color == EColorRed) ;
        __DD_ASSERT(parent == rbtree->root && parent->color == EColorBlack) ;
    }
}


static void _insert(dd_rbtree_tree* rbtree, dd_rbtree_node* node, dd_rbtree_key* key, dd_rbtree_value* value)
{
    int cmp = 0 ;
    
    __DD_ASSERT_DEFENSE(rbtree && node && key, return) ;
    
    if (node->key == DD_NULL) {
        __DD_ASSERT(node == rbtree->root) ;
        node->key    = key ;
        node->value  = value ;
        _change_color(node, EColorBlack) ;
        return ;
    }
    
    _path_add(rbtree->path, node) ;

    cmp = rbtree->key_compare(key, node->key) ;
    
    if (cmp < 0) {
        
        if (node->left_child) {
            _insert(rbtree, node->left_child, key, value) ;
        }
        else {
            node->left_child = _init_node(key, value) ;
            _path_add(rbtree->path, node->left_child) ;
            _insert_check_balance(rbtree) ;
        }
        return ;
    }
    
    if (cmp > 0) {
        if (node->right_child) {
            _insert(rbtree, node->right_child, key, value) ;
        }
        else {
            node->right_child = _init_node(key, value) ;
            _path_add(rbtree->path, node->right_child) ;
            _insert_check_balance(rbtree) ;
        }
        return ;
    }
    
    /* cmp = 0 */
    rbtree->key_conflict(node->key, node->value, key, value) ;
}


static void _remove_check_balance(dd_rbtree_tree* rbtree) ;


static DD_BOOL _is_color_red(const dd_rbtree_node* node)
{
    return node && node->color == EColorRed ; 
}


static void _remove_pB_sR(dd_rbtree_tree* rbtree)   
{
    dd_rbtree_node* cur     = _path_remove(rbtree->path) ;
    dd_rbtree_node* parent  = _path_remove(rbtree->path) ;
    dd_rbtree_node* sibling = _is_left_child(cur, parent) ? parent->right_child : parent->left_child ;

    /* TODO: */
    if (_is_left_child(sibling, parent)) {

        parent->left_child   = sibling->right_child ;
        sibling->right_child = parent ;

        _change_color(parent->left_child, EColorRed) ;
    }
    else {
        parent->right_child = sibling->left_child ;
        sibling->left_child = parent ;

        if (!_is_color_red(parent->right_child->left_child) && !_is_color_red(parent->right_child->right_child)) {
            _change_color(parent->right_child, EColorRed) ;
        }
        else if (_is_color_red(parent->right_child->left_child)) {
            
        }
        else {

        }
    }
    
    _change_color(sibling, EColorBlack) ;

    _change_child_in_path(rbtree, sibling, parent) ;
}

static void _remove_pR_sB_lnB_rnB(dd_rbtree_tree* rbtree)
{
    dd_rbtree_node* cur     = _path_remove(rbtree->path) ;
    dd_rbtree_node* parent  = _path_remove(rbtree->path) ;
    dd_rbtree_node* sibling = _is_left_child(cur, parent) ? parent->right_child : parent->left_child ;

    _change_color(parent, EColorBlack) ;
    _change_color(sibling, EColorRed) ;
}

static void _remove_pB_sB_lnB_rnB(dd_rbtree_tree* rbtree)
{
    dd_rbtree_node* cur     = _path_remove(rbtree->path) ;
    dd_rbtree_node* parent  = _path_top(rbtree->path) ;
    dd_rbtree_node* sibling = _is_left_child(cur, parent) ? parent->right_child : parent->left_child ;

    _change_color(sibling, EColorRed) ;
    
    _remove_check_balance(rbtree) ;
}

static void _remove_sB_rnR(dd_rbtree_tree* rbtree)
{
    dd_rbtree_node* cur     = _path_remove(rbtree->path) ;
    dd_rbtree_node* parent  = _path_remove(rbtree->path) ;
    dd_rbtree_node* sibling = _is_left_child(cur, parent) ? parent->right_child : parent->left_child ;
    dd_rbtree_node* rnephew = sibling->right_child ;

    if (_is_left_child(sibling, parent)) {

        parent->left_child   = rnephew->right_child ;
        sibling->right_child = rnephew->left_child ;

        rnephew->left_child  = sibling ;
        rnephew->right_child = parent ;

        _change_color(rnephew, (dd_rbtree_color)parent->color) ;
        _change_color(parent, EColorBlack) ;
        _change_color(sibling, EColorBlack) ;
        
        _change_child_in_path(rbtree, rnephew, parent) ;
    }
    else {
        parent->right_child = sibling->left_child ;
        sibling->left_child = parent ;
        
        _change_color(sibling, (dd_rbtree_color)parent->color) ;
        _change_color(parent, EColorBlack) ;
        _change_color(rnephew, EColorBlack) ;
        
        _change_child_in_path(rbtree, sibling, parent) ;
    }
}

static void _remove_sB_lnR(dd_rbtree_tree* rbtree)
{
    dd_rbtree_node* cur     = _path_remove(rbtree->path) ;
    dd_rbtree_node* parent  = _path_remove(rbtree->path) ;
    dd_rbtree_node* sibling = _is_left_child(cur, parent) ? parent->right_child : parent->left_child ;
    dd_rbtree_node* lnephew = sibling->left_child ;

    if (_is_left_child(sibling, parent)) {
        parent->left_child   = sibling->right_child ;
        sibling->right_child = parent ;
        _change_color(sibling, (dd_rbtree_color)parent->color) ;
        _change_color(parent, EColorBlack) ;
        _change_color(lnephew, EColorBlack) ;

        _change_child_in_path(rbtree, sibling, parent) ;
    }
    else {
        parent->right_child  = lnephew->left_child ;
        sibling->left_child  = lnephew->right_child ;
        lnephew->left_child  = parent ;
        lnephew->right_child = sibling ;

        _change_color(lnephew, (dd_rbtree_color)parent->color) ;
        _change_color(parent, EColorBlack) ;
        _change_color(sibling, EColorBlack) ;
        _change_child_in_path(rbtree, lnephew, parent) ;
    }
}

static void _remove_check_balance(dd_rbtree_tree* rbtree)
{
    dd_rbtree_node* parent  = DD_NULL;
    dd_rbtree_node* sibling = DD_NULL ;
    
    if(_path_count(rbtree->path) <= 1) 
        return ;

    parent  = _path_datan(rbtree->path, 1) ;
    sibling = _is_left_child(_path_top(rbtree->path), parent) ? parent->right_child : parent->left_child ;

    if (sibling->color == EColorBlack) {
        if (sibling->left_child && sibling->left_child->color == EColorRed)
            _remove_sB_lnR(rbtree) ;
        else if (sibling->right_child && sibling->right_child->color == EColorRed)
            _remove_sB_rnR(rbtree) ;
        else {
            if (parent->color == EColorBlack) 
                _remove_pB_sB_lnB_rnB(rbtree) ;
            else 
                _remove_pR_sB_lnB_rnB(rbtree) ;
        }
    }
    else {
        _remove_pB_sR(rbtree) ;
    }
}


static void _del_check_balance(dd_rbtree_tree* rbtree)
{
    /* The top node in path is the node to be removed, and it's a leaf or only have one child */
    DD_INT count            = _path_count(rbtree->path) ;
    dd_rbtree_node* del     = _path_top(rbtree->path) ;
    dd_rbtree_node* replace = DD_NULL ;
    dd_rbtree_node* parent  = DD_NULL;
    
    __DD_ASSERT_DEFENSE(count > 0, return) ;
    __DD_ASSERT(!(del->left_child && del->right_child)) ;
    __DD_ASSERT(_is_leaf(del) || (del->left_child ? del->left_child->color : del->right_child->color) == EColorRed) ;
    __DD_ASSERT(del->color != EColorRed || _is_leaf(del)) ;

    if (count == 1) {
        __DD_ASSERT(del == rbtree->root) ;
        del->key   = DD_NULL ;
        del->value = DD_NULL ;
        _deinit_node(del) ;
        return ;
    }
    
    replace = del->left_child ? del->left_child : del->right_child ;
    parent  = _path_datan(rbtree->path, 1) ;

    if (del->color == EColorRed) 
        goto Finish ;
 
    /* del's color is BLACK */

    __DD_ASSERT(!replace || replace->color == EColorRed) ;

    if (replace) {
        _change_color(replace, EColorBlack) ;
        goto Finish ;
    }
    
    /* del's color is BLACK and replace is NULL(color is BLACK) */

    _remove_check_balance(rbtree) ;

    Finish:
    if (_is_left_child(del, parent))
        parent->left_child  = replace ;
    else 
        parent->right_child = replace ;

    _deinit_node(del) ;
}


dd_rbtree_value* _remove(dd_rbtree_tree* rbtree, dd_rbtree_node* node, dd_rbtree_key* key) 
{
    int cmp              = 0 ;
    dd_rbtree_value* ret = DD_NULL ;

    __DD_ASSERT_DEFENSE(rbtree && key, return DD_NULL) ;
    
    if (!node)
        return DD_NULL ;

    _path_add(rbtree->path, node) ;
    
    cmp = rbtree->key_compare(key, node->key) ;

    if (cmp < 0)
        return _remove(rbtree, node->left_child, key) ;
    
    if (cmp > 0) 
        return _remove(rbtree, node->right_child, key) ;

    ret = node->value ;

    if (node->left_child) {
        dd_rbtree_node* tmp_node = node->left_child ;
        do {
            _path_add(rbtree->path, tmp_node) ;
            tmp_node = tmp_node->right_child ;
        } while (tmp_node);
    }
    else if (node->right_child) {
        dd_rbtree_node* tmp_node = node->right_child ;
        do {
            _path_add(rbtree->path, tmp_node) ;
            tmp_node = tmp_node->left_child ;
        } while (tmp_node);
    }
    
    node->key   = _path_top(rbtree->path)->key ;
    node->value = _path_top(rbtree->path)->value ;

    _del_check_balance(rbtree) ;

    return ret ;
}


dd_rbtree_tree* dd_rbtree_create(
    DD_INT (*key_compare)(const dd_rbtree_key*, const dd_rbtree_key*), 
    void (*key_conflict)(dd_rbtree_key* , dd_rbtree_value*, dd_rbtree_key*, dd_rbtree_value*) 
 ) 
{
    dd_rbtree_tree* rbtree = (dd_rbtree_tree*)DD_MALLOC(sizeof(dd_rbtree_tree)) ;
    DD_MEMSET(rbtree, 0, sizeof(dd_rbtree_tree)) ;
    
    rbtree->root          = _init_node(DD_NULL, DD_NULL) ;
    rbtree->path          = dd_stack_create(64) ;   /* 64-height is bigger enough to save all the sand in the earth, and stack can auto increase it's space too */
    rbtree->key_compare	  = key_compare ;
    rbtree->key_conflict  = key_conflict ;
    
    return rbtree ;
}

void dd_rbtree_destroy(dd_rbtree_tree* rbtree) 
{
    __DD_ASSERT_DEFENSE(rbtree, return) ;
    
    dd_stack_destroy(rbtree->path) ;
    _deinit_node(rbtree->root) ;
    __do_destroy(rbtree) ;
}


dd_rbtree_value* dd_rbtree_find(const dd_rbtree_tree* rbtree, dd_rbtree_key* key)
{
    dd_rbtree_node* tmp_node = rbtree->root ;
    
    __DD_ASSERT_DEFENSE(rbtree && rbtree->root && key, return DD_NULL) ;
    
    rbtree_Find:
    if (tmp_node) {
        
        int cmp = rbtree->key_compare(tmp_node->key, key) ;
        
        if (cmp < 0) {
            tmp_node = tmp_node->right_child ;
            goto rbtree_Find ;
        }
        
        if (cmp > 0) {
            tmp_node = tmp_node->left_child ;
            goto rbtree_Find ;
        }
        
        return tmp_node->value ;        
    }
    
    return DD_NULL ;
}


void dd_rbtree_insert(dd_rbtree_tree* rbtree, dd_rbtree_key* key, dd_rbtree_value* value) 
{
    __DD_ASSERT_DEFENSE(rbtree && rbtree->root && key, return) ;
    
    _path_clear(rbtree->path) ;

    _insert(rbtree, rbtree->root, key, value) ;
}


dd_rbtree_value* dd_rbtree_remove(dd_rbtree_tree* rbtree, dd_rbtree_key* key) 
{
    __DD_ASSERT_DEFENSE(rbtree && rbtree->root && key, return DD_NULL) ;
    
    _path_clear(rbtree->path) ;

    return _remove(rbtree, rbtree->root, key) ;
}


#ifdef __DD_UNITTEST

#include "dd_vector.h"


static DD_INT _test_key_compare(const dd_rbtree_key* key1, const dd_rbtree_key* key2) 
{
    if (key1 < key2) return -1 ;
    
    if (key1 > key2) return 1 ;
    
    return 0 ;
}

static void _test_key_conflict(
    dd_rbtree_key* key_found_conflict, 
    dd_rbtree_value* value_found_conflict, 
    dd_rbtree_key* key_handle, 
    dd_rbtree_value* value_handle
) 
{
    __DD_ASSERT((DD_INT)key_found_conflict == (DD_INT)value_found_conflict && (DD_INT)key_handle == (DD_INT)value_handle 
        && (DD_INT)key_found_conflict == (DD_INT)key_handle) ;
}


static DD_INT _sg_black_count = 0 ;


static DD_BOOL _ut_check_rbtree_node(dd_rbtree_tree* rbtree, dd_rbtree_node* node, DD_INT black_count)
{
    if (!node || node->color == EColorBlack)
        black_count++ ;
    
    if (!node) {
        if (_sg_black_count == 0) {
            _sg_black_count = black_count ;
        }
        else {
            if (_sg_black_count != black_count) {
                DD_LOG("_ut_check_rbtree_node ERROR the black node count is NOT match") ;
                return DD_FALSE ;
            }
        }
        return DD_TRUE;
    }
    
    if (node->color == EColorRed) {
        if (node->left_child && node->left_child->color == EColorRed) {
            DD_LOG("_ut_check_rbtree_node ERROR the node and his left child is all RED TOO") ;
            return DD_FALSE ;
        }
        
        if (node->right_child && node->right_child->color == EColorRed) {
            DD_LOG("_ut_check_rbtree_node ERROR the node and his right child is all RED TOO") ;
            return DD_FALSE ;
        }
    }
    
    if (node->left_child && rbtree->key_compare(node->left_child->key, node->key) >= 0) {
        DD_LOG("_ut_check_rbtree_node ERROR left key bigger than node key") ;
        return DD_FALSE ;
    }

    if (node->right_child && rbtree->key_compare(node->right_child->key, node->key) <= 0) {
        DD_LOG("_ut_check_rbtree_node ERROR right key smaller than node key") ;
        return DD_FALSE ;
    }

    if (!_ut_check_rbtree_node(rbtree, node->left_child, black_count))
        return DD_FALSE ;

    if (!_ut_check_rbtree_node(rbtree, node->right_child, black_count))
        return DD_FALSE ;

    return DD_TRUE ;
}


static DD_BOOL _ut_check_rbtree(dd_rbtree_tree* rbtree)
{
    _sg_black_count = 0 ;

    if (rbtree->root->color != EColorBlack) {
        DD_LOG("_ut_check_rbtree ERROR The root color is NOT Black") ;
        return DD_FALSE ;
    }
    
    return _ut_check_rbtree_node(rbtree, rbtree->root, 0) ;
}


#define __TEST_TIMES            (100 + 1)
#define __TEST_RECUR_ERROR


DD_BOOL dd_rbtree_test() 
{
    dd_rbtree_tree* test_rbtree = dd_rbtree_create(_test_key_compare, _test_key_conflict) ;
    dd_vector* test_vec         = dd_vector_create(__TEST_TIMES) ;
    
    DD_INT i = 0 ;

    return DD_TRUE ;
    
#ifndef __TEST_RECUR_ERROR
    i = 1 ;
    DD_SRAND(DD_TIME(0)) ;
    for (; i < __TEST_TIMES; i++) {
        void* k = (void*)(DD_RAND());
        // void* k = (void*)i ;
        if (k!= 0 && dd_rbtree_find(test_rbtree, k) == DD_NULL) {
            
            dd_rbtree_insert(test_rbtree, k, k) ; 
            dd_vector_append(test_vec, k) ;
            
            if (!_ut_check_rbtree(test_rbtree)) {
                DD_LOG("dd_rbtree_insert insert date ERROR") ;
                return DD_FALSE ;
            }
        } 
    }
    
    dd_vector_dump_file(test_vec, "d:\\vec_rbtree_dump.txt");

    DD_LOG("dd_rbtree_test the block node count per path in rbtree = %d", _sg_black_count) ;

#else
    
    dd_vector_destroy(test_vec, DD_NULL) ;

    test_vec = dd_vector_read_file("d:\\vec_rbtree_dump.txt") ;
    
    i = 0 ;
    
    for (; i < dd_vector_count(test_vec); i++)
    {
        void* k = (void*)dd_vector_get(test_vec, i) ;
        dd_rbtree_insert(test_rbtree, k, k) ; 
    }

#endif
    
    i = 1;
    for (; i < dd_vector_count(test_vec); i++)
    {
        if( dd_rbtree_find(test_rbtree, dd_vector_get(test_vec, i)) != dd_vector_get(test_vec, i))
        {
            DD_LOG("dd_rbtree_find find date ERROR") ;
            return DD_FALSE ;
        }
    }

    i = 1 ;
    for (; i < dd_vector_count(test_vec); i++) {
        
        void* k = (void*)dd_vector_get(test_vec, i) ;

        if (dd_rbtree_remove(test_rbtree, k) != k) {
            DD_LOG("dd_rbtree_remove remove date ERROR %d", (DD_INT)k) ;
            return DD_FALSE ;
        }
        
        if (!_ut_check_rbtree(test_rbtree))
            return DD_FALSE ;
    }

    dd_vector_destroy(test_vec, DD_NULL) ;
    dd_rbtree_destroy(test_rbtree) ;

    return DD_TRUE ;
}

#endif /* __DD_UNITTEST */


/* End of File */
